\documentclass{report}
\usepackage[UTF8]{ctex}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{mathrsfs} %导入花体数学字母
\usepackage{caption}
\usepackage{graphicx, subfig} %插入图片
\usepackage{listings} %插入代码
\usepackage{xcolor} %语法高亮
\usepackage{fontspec} %字体包
\usepackage{diagbox} % 斜线表头
\usepackage{geometry} %设置页面
\usepackage{enumerate}
\usepackage[colorlinks,linkcolor=blue]{hyperref} %超链接
\usepackage{marginnote} % 在正文旁边添加注释文字

\setlength{\marginparwidth}{0.6in} %页边空白处设定宽度0.6英寸
\let\oldmarginpar\marginpar
\renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize\color{red} #1]%
	{\raggedright\footnotesize\color{red} #1}} % 注释文字用红色footnote 大小
\marginparsep = 10pt %与正文间隔10pt

% \marginpar{需要添加的内容}
% 显示或隐藏页边注释，只要在文件头添加下面的语句，把它注释掉后又显示页边内容
% \renewcommand{\marginpar}[2][]{}

\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}

\usepackage{fancyhdr}
\usepackage{lipsum}
\pagestyle{fancy}

\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\sectionmark}[1]{\markright{\arabic{section}.\ #1}}
\lhead[\thepage]{\leftmark} 
\rhead[\nouppercase{\rightmark}]{\thepage}

\lstset{
	columns=fixed,       
	numbers=left,                                        % 在左侧显示行号
	numberstyle=\color{black},                       % 设定行号格式
	basicstyle=\fontspec{Consolas}\small\color[RGB]{212,212,212},
	tabsize=4,
	frame=single,                                        % 背景边框
	rulecolor=\color[rgb]{0,0,0},                  % 边框颜色
	extendedchars=false,                                 % 解决换页问题
	backgroundcolor=\color[RGB]{30,30,30},            % 设定背景颜色
	keywordstyle=\color[RGB]{156,220,254},                 % 设定关键字颜色
	identifierstyle=\color[RGB]{86,156,214},                       % 普通标识符颜色
	commentstyle=\it\color[RGB]{106,153,73},                % 设置代码注释的格式
	stringstyle=\rmfamily\slshape\color[RGB]{206,145,91},   % 设置字符串格式
	showstringspaces=false,                              % 不显示字符串中的空格
	language=c++,                                        % 设置语言
	escapeinside=``,                                     % 逃逸字符
	xleftmargin=1em,                                     % 边距设置
	xrightmargin=1em, 
	aboveskip=1em
}

\title{{\Huge Homework2\\ 数值分析}}
\author{{\LARGE 3190105815 信息与计算科学\ 行一凡}}
\date{{\LARGE \today}}

\begin{document}
	\maketitle
	\section*{Exercise I}
	\begin{itemize}
		\item 应用Lagrange formula，可得
		\begin{equation}\label{key}
			p_1(f;x) = f(x_0)\dfrac{x-x_1}{x_0-x_1} + f(x_1)\dfrac{x-x_0}{x_1-x_0}
		\end{equation}
		代入$ f(x) = \frac{1}{x},\ x_0=1,\ x_1=2 $，则有
		\begin{equation}\label{key}
			\dfrac{1}{x} + (x-2) - \dfrac{1}{2}(x-1) = \dfrac{f^{\prime\prime}(\xi(x))}{2}(x-1)(x-2) = \dfrac{(x-1)(x-2)}{\xi^3(x)}
		\end{equation}
		解得$ \xi(x) = \sqrt[3]{2x} $.
		
		\item $ \max\xi(x) = \xi(2) = \sqrt[3]{4},\ \min\xi(x) = \xi(1) = \sqrt[3]{2},\ \max f^{\prime\prime}(\xi(x)) =\max \frac{1}{x} = 1. $
	\end{itemize}

	\section*{Exercise II}
	利用Lagrange formula的构造方法，先有
	\begin{equation}\label{key}
		p(x) = \sum_{i=0}^{n}f_i\prod_{j\neq i}\dfrac{(x-x_j)}{(x_i-x_j)}
	\end{equation}
	则$ p(x) $是满足$ p(x_i) = f_i $的不高于n次多项式；由于$ f_i\ge 0 $，且需要$ p(x) $非负，从而可改写为
	\begin{equation}\label{key}
		p(x) = \sum_{i=0}^{n}f_i\left(\prod_{j\neq i}\dfrac{(x-x_j)}{(x_i-x_j)}\right)^2
	\end{equation}
	所得$ p(x) $仍然满足$ p(x_i) = f_i $，且$ p\in \mathbb{P}_{2n}^+ $，从而$ p $即为所求多项式。
	
	\section*{Exercise III}
	\begin{itemize}
		\item 应用归纳法，当$ n=0 $时，$ f[t] = f(t) = e^t $，满足公式；设对$ n = k-1 $成立，则
		\begin{equation}\label{key}
			f[t,t+1,\dots,t+k-1] = \dfrac{(e-1)^{k-1}}{(k-1)!}e^t
		\end{equation}
		\begin{equation}\label{key}
			f[t+1,t+2,\dots,t+k] = \dfrac{(e-1)^{k-1}}{(k-1)!}e^{t+1}
		\end{equation}
		根据递推公式，有
		\begin{equation}\label{key}
			\begin{aligned}
				f[t,t+1,\dots,t+k] &= \dfrac{f[t+1,t+2,\dots,t+k]-f[t,t+1,\dots,t+k-1]}{k}\\ 
				&= \dfrac{\frac{(e-1)^{k-1}}{(k-1)!}e^{t+1} - \frac{(e-1)^{k-1}}{(k-1)!}e^t}{k}\\ 
				&= \dfrac{(e-1)^{k}}{k!}e^{t}
			\end{aligned}
		\end{equation}
		由归纳假设即证。
	
		\item 在上一问中取$ t=0 $，则有
		\begin{equation}\label{key}
			\dfrac{(e-1)^n}{n!} = \dfrac{1}{n!}f^{(n)}(\xi) = \dfrac{1}{n!}e^{\xi}
		\end{equation}
		从而有$ \xi = n\ln(e-1) $，而$ \ln(e-1) > \frac{1}{2} $，故$ \xi $在中点的右侧。
	\end{itemize}
	
	\section*{Exercise IV}
	\begin{itemize}
		\item 计算差分表得到
		\begin{center}
			\begin{tabular}{c|cccc}
				$ 0 $ & 5 & & &\\ 
				$ 1 $ & 3 & -2 & &\\ 
				$ 3 $ & 5 & 1 & 1 &\\ 
				$ 4 $ & 12 & 7 & 2 & $ \dfrac{1}{4} $
			\end{tabular}
		\end{center}
		从而由Newton formula，有
		\begin{equation}\label{key}
			\begin{aligned}
				p_3(f;x) &= 5 + (-2)x + x(x-1) + \dfrac{1}{4}x(x-1)(x-3)\\ 
				&= \frac{1}{4}x^3 - \dfrac{9}{4}x + 5
			\end{aligned}
		\end{equation}
	
		\item 对$ p_3(f;x) $求导得
		\begin{equation}\label{key}
			p_3^{\prime}(f;x) = \dfrac{3}{4}x^2 - \dfrac{9}{4}
		\end{equation}
		则$ p_3 $在$ x=\sqrt{3} $处有极值；且当$ 1<x<\sqrt{3} $时，$ p_3^{\prime}<0 $，当$ 3>x>\sqrt{3} $时，$ p_3^{\prime}>0 $，故$ x = \sqrt{3} $即为估计最小值点。
	\end{itemize}

	\section*{Exercise V}
	\begin{itemize}
		\item 计算差分表得到
		\begin{center}
			\begin{tabular}{c|cccccc}
				0 & 0 & & & & &\\ 
				1 & 1 & 1 & & & &\\ 
				1 & 1 & 7 & 6 & & &\\ 
				1 & 1 & 7 & 21 & 15 & &\\ 
				2 & 128 & 127 & 120 & 99 & 42 &\\ 
				2 & 128 & 448 & 321 & 201 & 102 & 30
			\end{tabular}
		\end{center}
		从而$ f[0,1,1,1,2,2] = 30 $.
		
		\item $ f[x_0,x_1,\dots,x_5] = \frac{1}{5!}f^{(5)}(\xi) = 21\xi^2 $，从而$ \xi = \sqrt{\frac{10}{7}} $.
	\end{itemize}

	\section*{Exercise VI}
	\begin{itemize}
		\item 计算差分表得到
		\begin{center}
			\begin{tabular}{c|ccccc}
				0 & 1 & & & & \\ 
				1 & 2 & 1 & & & \\ 
				1 & 2 & -1 & -2 & & \\ 
				3 & 0 & -1 & 0 & $ \frac{2}{3} $ & \\ 
				3 & 0 & 0 & $ \frac{1}{2} $ & $ \frac{1}{4} $ & $ -\frac{5}{36} $
		\end{tabular}
		\end{center}
		从而有插值多项式
		\begin{equation}\label{key}
			p(x) = 1 + x + (-2)x(x-1) + \dfrac{2}{3}x(x-1)^2 + (-\dfrac{5}{36})x(x-1)^2(x-3)
		\end{equation}
		代入$ x=2 $得$ f(2)=\frac{11}{18} $.
		
		\item 由插值多项式的余项
		\begin{equation}\label{key}
			R_n(f;x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)
		\end{equation}
		代入可得
		\begin{equation}\label{key}
			R_4(f;x) = \dfrac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2
		\end{equation}
		对$ p(x) = x(x-1)^2(x-3)^2 $求导得到
		\begin{equation}\label{key}
			p^{\prime}(x) = \left(x-\dfrac{6}{5} + \dfrac{\sqrt{21}}{5}\right)\left(x+\dfrac{6}{5} - \dfrac{\sqrt{21}}{5}\right)(x-1)(x-3)
		\end{equation}
		代入边界端点和极值点得到$ \max|p(x)|\thickapprox2.05944 $，故$ \max |R_4(f;x)|\le 0.017162M $.
	\end{itemize}

	\section*{Exercise VII}
	应用数学归纳法，对$ k=1 $由定义显然成立；设对$ k $成立，则有
	\begin{equation}\label{key}
		\begin{aligned}
			\Delta^{k+1}f(x) &= \Delta\Delta^kf(x) = \Delta^kf(x+h) - \Delta^kf(x)\\ 
			&= k!h^k f[x_1,x_2,\dots,x_{k+1}] - k!h^k f[x_0,x_1,\dots,x_{k}]\\ 
			&= k!h^k (x_{k+1}-x_0)\cdot\dfrac{f[x_1,x_2,\dots,x_{k+1}] - f[x_0,x_1,\dots,x_{k}]}{x_{k+1}-x_0}\\ 
			&= (k+1)!h^{k+1} f[x_0,x_1,\dots,x_{k+1}]
		\end{aligned}
	\end{equation}
	同理有
	\begin{equation}\label{key}
		\begin{aligned}
			\nabla^{k+1}f(x) &= \nabla\nabla^kf(x) = \nabla^kf(x) - \nabla^kf(x-h)\\ 
			&= k!h^k f[x_0,x_{-1},\dots,x_{-k}] - k!h^k f[x_{-1},x_{-2},\dots,x_{-k-1}]\\ 
			&= k!h^k (x_0-x_{-k-1})\cdot\dfrac{f[x_{-1},x_{-2},\dots,x_{-k-1}]-f[x_0,x_{-1},\dots,x_{-k}]}{x_{-k-1}-x_0}\\ 
			&= (k+1)!h^{k+1} f[x_0,x_1,\dots,x_{-k-1}]
		\end{aligned}
	\end{equation}
	从而由归纳假设成立。
	
	\section*{Exercise VIII}
	应用数学归纳法，对$ n=0 $有$ \frac{\partial}{\partial x_0}f[x_0] = \frac{\partial f(x_0)}{\partial x_0} = f[x_0,x_0] $成立；设对$ n $成立，则有
	\begin{equation}\label{key}
		\begin{aligned}
			\dfrac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_{n+1}] &= \dfrac{\partial}{\partial x_0} \dfrac{f[x_0,x_1,\dots,x_n]-f[x_1,x_2,\dots,x_{n+1}]}{x_{n+1}-x_0}\\ 
			&= \dfrac{f[x_0,x_0,x_1,\dots,x_n](x_{n+1}-x_0)+f[x_0,x_1,\dots,x_n]-f[x_1,x_2,\dots,x_{n+1}]}{(x_{n+1}-x_0)^2}\\ 
			&= \dfrac{f[x_0,x_0,x_1,\dots,x_n]-f[x_0,x_1,\dots,x_{n+1}]}{x_{n+1}-x_0}\\ 
			&= f[x_0,x_0,x_1,\dots,x_{n+1}]
		\end{aligned}
	\end{equation}
	从而由归纳假设成立。
	
	\section*{Exercise IX}
	对任意多项式
	\begin{equation}\label{key}
		p(x) = a_0x^n+a_1x^{n-1}+\cdots+a_n,\ x\in[a,b]
	\end{equation}
	先做平移代换$ y = x - \frac{a+b}{2} $得
	\begin{equation}\label{key}
		\begin{aligned}
			p(y) &= a_0\left(y+\dfrac{a+b}{2}\right)^n+a_1\left(y+\dfrac{a+b}{2}\right)^{n-1}+\cdots+a_n,\\ 
			&= b_0y^n+b_1y^{n-1}+\cdots+b_n,\ y\in\left[-\frac{b-a}{2},\frac{b-a}{2}\right]
		\end{aligned}
	\end{equation}
	再做伸缩变换$ t = \frac{2}{b-a}y $得
	\begin{equation}\label{key}
		\begin{aligned}
			p(t) &= b_0\left(\dfrac{b-a}{2}t\right)^n+b_1\left(\dfrac{b-a}{2}t\right)^{n-1}+\cdots+b_n,\\ 
			&= c_0t^n+c_1t^{n-1}+\cdots+c_n,\ t\in[-1,1]
		\end{aligned}
	\end{equation}
	则其中$ c_0 = b_0(\frac{b-a}{2})^n = a_0(\frac{b-a}{2})^n $；由Corollary 3.41，首一多项式$ \left|\frac{p(t)}{c_0}\right| $满足
	\begin{equation}\label{key}
		\max_{t\in[-1,1]} \left|\dfrac{p(t)}{c_0}\right| \ge \dfrac{1}{2^{n-1}}
	\end{equation}
	且存在首一化的Chebyshev多项式可取得等号，故有
	\begin{equation}\label{key}
		\min\max_{t\in[-1,1]}|p(t)| = \dfrac{c_0}{2^{n-1}} = \dfrac{a_0(b-a)^n}{2^{2n-1}}
	\end{equation}
	由于上述代换是可逆等价代换，从而有
	\begin{equation}\label{key}
		\min\max_{x\in[a,b]}|a_0x^n+a_1x^{n-1}+\cdots+a_n| = \dfrac{a_0(b-a)^n}{2^{2n-1}}
	\end{equation}

	\section*{Exercise X}
	反设$ \exists p\in \mathbb{P}_n^a,\ s.t.\ \lVert p\lVert_{\infty} \le \lVert \hat{p}_n(x)\lVert_{\infty} = \left|\frac{1}{T_n(a)}\right| $，令$ Q(x) = \hat{p}_n(x) - p $，则在$ T_n(x) $的极值点$ x_i$有
	\begin{equation}\label{key}
		Q(x_i) = \frac{(-1)^k}{T_n(a)} - p(x_i),\ i=0,1,\dots,n
	\end{equation}
	从而$ Q(x) $在$ x_i $处交替符号，故在$ [-1,1] $上有$ n $个零点；而由$ \hat{p}_n(x) $的构造，
	\begin{equation}\label{key}
		Q(a) = \hat{p}_n(a) - p(a) = 0
	\end{equation}
	则$ x=a>1 $也是$ Q(x) $的零点，从而$ Q(x) $存在$ n+1 $个零点，至少是$ n+1 $阶多项式，而由$ Q(x) $的构造，$ Q(x) $至多是$ n $阶多项式，推出矛盾。
	
\end{document}